package offer.zixing.chapter02;

/**
 * 二维子矩阵的和
 *
 * 输入一个二维矩阵，如何计算给定左上角坐标和右下角坐标的子矩阵数字之和？
 * 对同一个二维矩阵，计算子矩阵数字之和的函数可能输入不同的坐标而被反复调用多次。
 * 例如输入图2.1中的二维矩阵，以及左上角坐标为(2, 1)和右下角坐标为(4, 3)，该函数输出8。
 *                 {3, 0, 1, 4, 2},
 *                 {5, 6, 3, 2, 1},
 *                 {1, 2, 0, 1, 5},
 *                 {4, 1, 0, 1, 7},
 *                 {1, 0, 3, 0, 5}
 */
public class Test013 {
    public static void main(String[] args) {
        int[][] A = new int[][]{{1,2}, {2,3,4}, {1,2,3,4}};
        System.out.println(A[0][1]);
        int[][] matrix = new int[][]{
                {3, 0, 1, 4, 2},
                {5, 6, 3, 2, 1},
                {1, 2, 0, 1, 5},
                {4, 1, 0, 1, 7},
                {1, 0, 3, 0, 5}
        };
        NumMatrix numMatrix = new NumMatrix(matrix);
        System.out.println(numMatrix.sumRegion(0,0,1,1));
    }
}

class NumMatrix {
    private int[][] sums;

    NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        sums = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            int rowSum = 0;
            for (int j = 0; j < matrix[0].length; j++) {
                rowSum += matrix[i][j];
                sums[i + 1][j + 1] = sums[i][j + 1] + rowSum;
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1]
                - sums[row2 + 1][col1] + sums[row1][col1];
    }
}
